package com.cn.codebrush.数组.回溯;

public class No79单词搜索 {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}}; //word = "ABCCED"  word = "ABCB"  "ABCESEEEFS"
        System.out.println(exist(board,"ABCESEEEFS"));

    }

    public static boolean exist(char[][] board, String word) {
        int m = board[0].length;
        int n = board.length;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j] == word.charAt(0)){
                    boolean[][] dp = new boolean[n][m];
                    dp[i][j] = true;
                    if(existHelper(board,word,""+word.charAt(0),0,i,j,dp)){
                        return true;
                    }
                }
            }
        }

        return false;
    }


    public static boolean existHelper(char[][] board, String word,String temp,int index,int i,int j,boolean[][] dp) {
        if(word.equals(temp)){
            return true;
        }
        if(temp.length() == word.length()){
            return false;
        }

        //上
        if(i-1>=0 && !dp[i-1][j] && board[i-1][j] == word.charAt(index+1)){
            dp[i-1][j] = true;
            if(existHelper(board,word,temp+word.charAt(index+1),index+1,i-1,j,dp)){
                return true;
            }else {
                dp[i-1][j] = false;
            }
        }
        //左
        if(j-1>=0 && !dp[i][j-1] && board[i][j-1] == word.charAt(index+1)){
            dp[i][j-1] = true;
            if(existHelper(board,word,temp+word.charAt(index+1),index+1,i,j-1,dp)){
                return true;
            }else {
                dp[i][j-1] = false;
            }
        }
        //右
        if(j+1< board[0].length && !dp[i][j+1] && board[i][j+1] == word.charAt(index+1)){
            dp[i][j+1] = true;
            if(existHelper(board,word,temp+word.charAt(index+1),index+1,i,j+1,dp)){
                return true;
            }else {
                dp[i][j+1] = false;
            }
        }
        //下
        if(i+1< board.length && !dp[i+1][j] && board[i+1][j] == word.charAt(index+1)){
            dp[i+1][j] = true;
            if(existHelper(board,word,temp+word.charAt(index+1),index+1,i+1,j,dp)){
                return true;
            }else {
                dp[i+1][j] = false;
            }
        }


        return false;
    }

}
